package com.example.myproject.suanfa.exchange;

import java.util.Arrays;

/**
 * 冒泡排序算法的运作如下:
 *  1 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 2 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 *  3针对所有的元素重复以上的步骤，除了最后一个。
 *  4 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
 *
 * 有的冒泡经过第一轮的交换已经是有序的了，如：2 1 3 4。数据越多的时候越慢，非常不适合大数据的排序
 *
 * 解决办法
 * 如果用一个flag来判断一下，当前数组是否已经有序，如果有序就退出循环，这样可以明显的提高冒泡排序的性能。
 *
 */
public class BubbleSortDemo {

    public static void bubbleSort(int[] source){
       //外层循环控制循环次数，第1次得到最后一次最大值，第2次到倒数第2个次大，第n-1才，第2个最大的，第1个不需要排了
        //所以n-1次排序,就把第2个到第length个都排序好了
        int temp = 0;
       int length = source.length;
       for(int i= 1;i< length;i++) {
           //j+1 <= n-i 这个是要比较的最大的下标；
           for(int j=0;j<=(length-1-i);j++){
               if(source[j] > source[j+1]){
                   temp  = source[j];
                   source[j]=source[j+1];
                   source[j+1] = temp;
               }
           }
       }
    }


    public static void bubbleSortOption(int[] source){
        //外层循环控制循环次数，第1次得到最后一次最大值，第2次到倒数第2个次大，第n-1才，第2个最大的，第1个不需要排了
        //所以n-1次排序,就把第2个到第length个都排序好了
        int length = source.length;
        int temp = 0;
        for(int i= 1;i< length;i++) {
            boolean flag = false;
            //j+1 <= n-i 这个是要比较的最大的下标；
            //考虑j+1 是最后一个下标要放的位置,n-i;
            for(int j= 0;j<=(length-1-i);j++){
                if(source[j] > source[j+1]){
                    temp  = source[j];
                    source[j]=source[j+1];
                    source[j+1] = temp;
                    flag = true;
                }
            }
            System.out.println("第"+i+"趟结果："+Arrays.toString(source));
            //判断标志位flag有没有发生变化，没有就直接结束外面的那层循环了，不需要比较了
            if(!flag){
                System.out.println("第："+i +",趟，已经是有序的了，就不需要排序了！");
                break;
            }
        }
    }


    public static void bubbleSort2(int[] source){
        //外层循环控制循环次数，第1次得到最后一次最大值，第2次到倒数第2个次大，第n-1才，第2个最大的，第1个不需要排了
        //所以n-1次排序
        int length = source.length;
        for(int i=0;i<length-1;i++) { //这个也有n-1趟排序了
            //j+1 <= n-i 这个是要比较的最大的下标；
            for(int j=0;j<(length-1-i);j++){
                if(source[j] > source[j+1]){
                    int temp = source[j];
                    source[j]=source[j+1];
                    source[j+1] = temp;
                }
            }
        }
    }


    public static void main(String[] args) {
        int arr[] = new int[]{2,1,3,4,5};
        bubbleSortOption(arr);
        System.out.println("排序后的结果："+Arrays.toString(arr));
    }

}
